package array.medium;

/**
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * <p>
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 */
public class sortColors {

    public static void main(String[] args) {
        int[] test = {2, 0, 2, 1, 2, 1, 0, 1};
        myCode2(test);
        for (int i : test) {
            System.out.println(i);
        }
    }

    /**
     * 暴力排序解法
     * 审题不准
     * 但适合所有排序
     * 时间复杂度高
     *
     * @param nums
     */
    public static void myCode(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = nums[i];
            int k = 0;
            for (int j = i; j < nums.length; j++) {
                if (min >= nums[j]) {
                    min = nums[j];
                    k = j;
                }
            }
            nums[k] = nums[i];
            nums[i] = min;
        }
    }

    /**
     * 但是这并不是一般的排序问题，数组中的元素只能是[0,1,2]
     * 单指针两次遍历，先将0放在数组最前面，再将1放在0后面
     *
     * @param nums
     */
    public static void myCode1(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                nums[i] = nums[k];
                nums[k++] = 0;
            }
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] == 1) {
                nums[i] = nums[k];
                nums[k++] = 1;
            }
        }
    }

    /**
     * 双指针方式
     * @param nums
     */
    public static void myCode2(int[] nums) {
        int p0 = 0;
        int p1 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                nums[i] = nums[p1];
                nums[p1] = 1;
                p1++;
            } else if (nums[i] == 0) {
                nums[i] = nums[p0];
                nums[p0] = 0;
                /**
                 * 若0出现在1后面则需要将与0交换的1再跟当前p1指针所指的元素交换一次
                 */
                if (p0 < p1) {
                    nums[i] = nums[p1];
                    nums[p1] = 1;
                }
                p0++;
                p1++;
            }
        }
    }
}
